翻訳と辞書 Words near each other ・ Double groupoid ・ Double H ・ Double H High Adventure Base ・ Double H Mountains ・ Double H Pipeline ・ Double hammer ・ Double Happiness ・ Double Happiness (album) ・ Double Happiness (calligraphy) ・ Double Happiness (cigarette) ・ Double Happiness (film) ・ Double Happiness (TV series) ・ Double harmonic scale ・ Double Harness ・ Double harness ・ Double hashing ・ Double Haven ・ Double Hawk ・ Double head ・ Double Head Cabbage ・ Double helix (disambiguation) ・ Double Helix (music composition) ・ Double Helix (novel) ・ Double Helix (The Outer Limits) ・ Double Helix Corporation ・ Double Helix Games ・ Double Helix Medal ・ Double Helix Nebula ・ Double Herm of Socrates and Seneca ・ Double hermeneutic Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Double hashing ： ウィキペディア英語版 Double hashing Double hashing is a computer programming technique used in hash tables to resolve hash collisions, cases when two different values to be searched for produce the same hash key. It is a popular collision-resolution technique in open-addressed hash tables. Double hashing is implemented in many popular libraries. Like linear probing, it uses one hash value as a starting point and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. Given two randomly, uniformly, and independently selected hash functions $h\_1$ and $h\_2$, the ''i''th location in the bucket sequence for value ''k'' in a hash table $T$ is: $h(i,k)=(h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k))\backslash mod\; |T|.$ Generally, $h\_1$ and $h\_2$ are selected from a set of universal hash functions. == Classical applied data structure == Double hashing with open addressing is a classical data structure on a table $T$. Let $n$ be the number of elements stored in $T$, then $T$'s load factor is $\backslash alpha\; =\; \backslash frac$. Double hashing approximates uniform open address hashing. That is, start by randomly, uniformly and independently selecting two universal hash functions $h\_1$ and $h\_2$ to build a double hashing table $T$. All elements are put in $T$ by double hashing using $h\_1$ and $h\_2$. Given a key $k$, determining the $(i+1)$-st hash location is computed by: $h(i,k)\; =\; (\; h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k)\; )\; \backslash mod\; |T|.$ Let $T$ have fixed load factor $\backslash alpha:\; 1\; >\; \backslash alpha\; >\; 0$. Bradford and Katehakis〔 P. G. Bradford and M. Katehakis: ''A Probabilistic Study on Combinatorial Expanders and Hashing'', SIAM Journal on Computing 2007 (37:1), 83-111. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.2647 〕 showed the expected number of probes for an unsuccessful search in $T$, still using these initially chosen hash functions, is $\backslash frac$ regardless of the distribution of the inputs. More precisely, these two uniformly, randomly and independently chosen hash functions are chosen from a set of universal hash functions where pair-wise independence suffices. Previous results include: Guibas and Szemerédi〔 L. Guibas and E. Szemerédi: ''The Analysis of Double Hashing'', Journal of Computer and System Sciences, 1978, 16, 226-274. 〕 showed $\backslash frac$ holds for unsuccessful search for load factors . Also, Lueker and Molodowitch〔 G. S. Lueker and M. Molodowitch: ''More Analysis of Double Hashing'', Combinatorica, 1993, 13(1), 83-96. 〕 showed this held assuming ideal randomized functions. Schmidt and Siegel〔 J. P. Schmidt and A. Siegel: ''Double Hashing is Computable and Randomizable with Universal Hash Functions'', manuscript. 〕 showed this with $k$-wise independent and uniform functions (for $k\; =\; c\; \backslash log\; n$, and suitable constant $c$). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Double hashing」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.